﻿// 0909train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;


/**/


/*
 园区某部门举办了Family Day，邀请员工及其家属参加;
 将公司园区视为一个矩形，起始园区设置在左上角，终点园区设置在右下角；
 家属参观园区时，只能向右和向下园区前进；求从起始园区到终点园区会有多少条不同的参观路径

输入描述
第一行为园区长和宽；后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观
1 <= 园区长, 园区宽 <= 100

输出描述
输出为不同的路径数量

输入
3 3
0 0 0
0 1 0
0 0 0
输出
2

 */
class Solution02
{
public:
    Solution02(vector<vector<int>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        vector<vector<long long>>dynamic_vec(row_size, vector<long long>(col_size));
        dynamic_vec[0][0] = 1;

        for (int r=0; r<row_size; r++)
        {
            if (grid[r][0] == 1) break;
            //第一列，只有1种方式
            dynamic_vec[r][0] = 1;
        }

        for (int c=0; c<col_size; c++)
        {
            if (grid[0][c] == 1) break;
            //第一行，只有1种方式
            dynamic_vec[0][c] = 1;
        }

        for (int r=1; r<row_size; r++)
        {
            for (int c=1; c<col_size; c++)
            {
                //1不能访问
                if (grid[r][c] == 1)continue;

                dynamic_vec[r][c] += dynamic_vec[r - 1][c];
                dynamic_vec[r][c] += dynamic_vec[r][c - 1];
            }
        }

        cout << dynamic_vec[row_size - 1][col_size - 1];
        //Solution02
    }

private:
    int row_size = 0, col_size = 0;
};


/*
 机器人搬砖，一共有N堆砖存放在N个不同的仓库中，
 第i堆砖中有bricks[i]块砖头，要求在8小时内搬完
 机器人每小时能搬砖的数量取决于有多少能量格，机器人一个小时中只能在一个仓库中搬砖，
 机器人的能量格每小时补充一次且能量格只在这一个小时有效，为使得机器人损耗最小化，
 尽量减小每次补充的能量格数。
为了保障在8小时内能完成搬砖任务，请计算每小时给机器人充能的最小能量格数。
备注:
1、无需考虑机器人补充能量格的耗时
2、无需考虑机器人搬砖的耗时
3、机器人每小时补充能量格只在这一个小时中有效。

输入描述
程序输入为"30 12 25 8 19"一个整数数组，数组中的每个数字代表第i堆砖的个数，每堆砖的个数不超过100

输出描述
输出在8小时内完成搬砖任务，机器人每小时最少需要充多少个能量格；
如果8个小时内无论如何都完成不了任务，则输出"-1"

输入
30 12 25 8 19

输出
15
*/
class Solution01
{
public:
    int computeTime(vector<int>&num_vec, int speed)
    {
        int sum_time = 0;

        for (auto&amount:num_vec)
        {
            sum_time += ceil(double(amount) / double(speed));
        }

        return sum_time;
        //computeTime
    }

    Solution01(vector<int>&num_vec)
    {
        int v_size = num_vec.size();
        sort(num_vec.begin(), num_vec.end());

        int left = 1, right = num_vec[v_size - 1] + 1;

        int result = INT_MAX;
        while (left<right)
        {
            int mid = left + (right - left) / 2;

            if (computeTime(num_vec, mid)<=8)
            {
                result = mid;
                //速度满足要求，继续减少速度
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }

        if (result==INT_MAX)
        {
            cout << -1;
            return;
        }

        cout << result;
        //Solution01
    }
};

int main()
{
	{
/*
3 3
0 0 0
0 1 0
0 0 0
*/
        int row_size, col_size;
        cin >> row_size >> col_size;
        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                cin >> grid[r][c];
            }
        }

        Solution02 solu(grid);

        return 0;
	}
    vector<int>num_vec;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (oh_sstream>>token)
    {
        num_vec.push_back(stod(token));
    }

    Solution01 solu(num_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
